class Solution(object):
    def shipWithinDays(self, weights, days):
        right = sum(weights)
        n = len(weights)
        left = sum(weights) // days

        def search(value):
            max_v = - float('inf')
            now = 0
            count = 0
            index = 0
            while index < n:
                if now + weights[index] > value:
                    max_v = max(max_v, now)
                    now = 0
                    count += 1
                    if count == days - 1:
                        break
                else:
                    now += weights[index]
                    index += 1
            max_v = max(max_v, sum(weights[index:]), now)
            return max_v

        while left < right:
            mid = (left + right) // 2
            value = search(mid)
            if value <= mid:
                right = mid
            else:
                left = mid + 1
        return right
